<meta charset="UTF-8" />

<canvas id="canvas"></canvas>

<style>
	#canvas {
		width: 700px;
		height: 700px;
	}
</style>

<script>
	/** @type { HTMLCanvasElement } */
	const canvas = document.getElementById("canvas");
	const context = canvas.getContext("2d");
	const canvasWieth = canvas.width = canvas.offsetWidth;
	const canvasHeight = canvas.height = canvas.offsetHeight;
	const padding = 10;

	/** @param map { sudoku_map } */
	const draw = function (map) {
		context.save();// draw background
		context.fillStyle = "#FFFFFF";
		context.fillRect(0, 0, canvasWieth, canvasHeight);
		context.restore();// draw background

		const width = canvasWieth - padding * 2;
		const height = canvasHeight - padding * 2;
		const threeWidth = width / 3;
		const threeHeight = height / 3;
		const nineWidth = width / 9;
		const nineHieght = height / 9;

		context.save();// translate
		context.translate(padding, padding);

		context.save();// draw nine axis
		context.strokeStyle = "#333";
		context.lineWidth = 1;
		for (let i = 0; i < 10; i++) {
			const x_pos = nineWidth * i;
			const y_pos = nineHieght * i;

			context.beginPath();
			context.moveTo(x_pos, 0);
			context.lineTo(x_pos, height);
			context.stroke();
			context.beginPath();
			context.moveTo(0, y_pos);
			context.lineTo(width, y_pos);
			context.stroke();
		}
		context.restore();// draw nine axis

		context.save();// draw three axis
		context.strokeStyle = "#000";
		context.lineWidth = 3;
		for (let i = 1; i < 3; i++) {
			const x_pos = threeWidth * i;
			const y_pos = threeHeight * i;

			context.beginPath();
			context.moveTo(x_pos, 0);
			context.lineTo(x_pos, height);
			context.stroke();
			context.beginPath();
			context.moveTo(0, y_pos);
			context.lineTo(width, y_pos);
			context.stroke();
		}
		context.restore();// draw three axis

		for (let y_pos = 0; y_pos < 9; y_pos++) {
			for (let x_pos = 0; x_pos < 9; x_pos++) {
				const y = y_pos * nineHieght;
				const x = x_pos * nineWidth;
				const y_center = y + nineHieght / 1.8;
				const x_center = x + nineWidth / 2;

				const value = map[y_pos][x_pos];

				if (typeof value === "number") {
					context.save();// draw value
					context.font = `${50}px 微软雅黑`;
					context.textAlign = "center";
					context.textBaseline = "middle";
					context.fillText(value.toString(), x_center, y_center);
					context.restore();// draw value
				} else {
					context.save();// draw value table

					context.font = `${16}px 微软雅黑`;
					context.textAlign = "center";
					context.textBaseline = "middle";

					const valuePadding = 6;
					const valueThreeHeight = (nineHieght - valuePadding * 2) / 3;
					const valueThreeWidth = (nineWidth - valuePadding * 2) / 3;

					context.translate(valuePadding, valuePadding);

					for (let value_y_pos = 0; value_y_pos < 3; value_y_pos++) {
						for (let value_x_pos = 0; value_x_pos < 3; value_x_pos++) {
							const tableValue = value_y_pos * 3 + value_x_pos + 1;
							if (value.has(tableValue)) {
								const value_y = y + value_y_pos * valueThreeHeight;
								const value_x = x + value_x_pos * valueThreeWidth;
								const value_y_center = value_y + valueThreeHeight / 1.8;
								const value_x_center = value_x + valueThreeWidth / 2;

								context.save();// draw table value
								context.fillText(tableValue.toString(), value_x_center, value_y_center);
								context.restore();// draw table value
							}
						}
					}
					context.restore();// draw value table
				}
			}
		}

		context.restore();// translate
	};
</script>

<script>

	/**
	 * 分割数组
	 * @template T 数组数据类型
	 * @param arr { T[] } 被分割数组
	 * @param length { number } 分割长度
	*/
	const array_split = (arr, length) => {
		const result = [];
		const arr_length = arr.length;
		const count = arr_length / length;
		for (let i = 0; i < count; i++) {
			const isEnd = i + 1 === count;
			result.push(arr.slice(i * length, isEnd ? arr_length : (i + 1) * length));
		}
		return result;
	};

	/** @typedef { number | Set<number>} sudoku_map_value */
	/** @typedef { sudoku_map_value[][] } sudoku_map */

	const getFullValueSet = () => new Set([1, 2, 3, 4, 5, 6, 7, 8, 9]);

	const judgeNumber = (value) => typeof value === "number";

	/**
	 * @param map { sudoku_map }
	 * @param p_y { number }
	 * @param p_x { number }
	 */
	const getSmallMapValueByPos = function (map, p_y, p_x) {
		const table_y = p_y - p_y % 3;
		const table_x = p_x - p_x % 3;

		/** @type { sudoku_map_value[] } */
		const result = [];

		for (let y_add = 0; y_add < 3; y_add++) {
			for (let x_add = 0; x_add < 3; x_add++) {
				const y = table_y + y_add;
				const x = table_x + x_add;

				if (!(y === p_y && x === p_x)) {
					result.push(map[y][x]);
				}
			}
		}

		return result;
	};

	/**
	 * @param map { sudoku_map }
	 * @param p_y { number }
	 * @param p_x { number }
	 */
	const getXAxisValueByPos = function (map, p_y, p_x) {
		/** @type { sudoku_map_value[] } */
		const result = [];

		for (let x = 0; x < 9; x++) {
			if (p_x !== x) {
				result.push(map[p_y][x]);
			}
		}

		return result;
	};

	/**
	 * @param map { sudoku_map }
	 * @param p_y { number }
	 * @param p_x { number }
	 */
	const getYAxisValueByPos = function (map, p_y, p_x) {
		/** @type { sudoku_map_value[] } */
		const result = [];

		for (let y = 0; y < 9; y++) {
			if (p_y !== y) {
				result.push(map[y][p_x]);
			}
		}

		return result;
	};

	/** @param map { sudoku_map } */
	const parseOne = function (map) {
		let untreated_count = 81;

		for (let y = 0; y < 9; y++) {
			for (let x = 0; x < 9; x++) {
				const value = map[y][x];

				if (typeof value === "number") {
					untreated_count--;
					continue;
				}

				const smallList = getSmallMapValueByPos(map, y, x);
				const xAxisList = getXAxisValueByPos(map, y, x);
				const yAxisList = getYAxisValueByPos(map, y, x);

				const axisList = [...xAxisList, ...yAxisList];

				/** @type { Set<number> } */ const valueSet = new Set([...smallList, ...axisList].filter(o => judgeNumber(o)));
				/** @type { Set<number> } */ const smallSet = new Set(smallList.map(o => judgeNumber(o) ? o : Array.from(o)).flat());
				/** @type { Set<number> } */ const xAxisSet = new Set(xAxisList.map(o => judgeNumber(o) ? o : Array.from(o)).flat());
				/** @type { Set<number> } */ const yAxisSet = new Set(yAxisList.map(o => judgeNumber(o) ? o : Array.from(o)).flat());

				/** @type { number[] } */ const smallValueList = smallList.filter(o => judgeNumber(o));
				/** @type { number[] } */ const xAxisValueList = xAxisList.filter(o => judgeNumber(o));
				/** @type { number[] } */ const yAxisValueList = yAxisList.filter(o => judgeNumber(o));

				/** @type { Set<number>[] } */ const smallTwoMapList = smallList.filter(o => !judgeNumber(o) && o.size === 2);
				/** @type { Set<number>[] } */ const xAxisTwoMapList = xAxisList.filter(o => !judgeNumber(o) && o.size === 2);
				/** @type { Set<number>[] } */ const yAxisTwoMapList = yAxisList.filter(o => !judgeNumber(o) && o.size === 2);

				/** @type { Set<number>[] } */ const smallThreeMapList = smallList.filter(o => !judgeNumber(o) && o.size === 3);
				/** @type { Set<number>[] } */ const xAxisThreeMapList = xAxisList.filter(o => !judgeNumber(o) && o.size === 3);
				/** @type { Set<number>[] } */ const yAxisThreeMapList = yAxisList.filter(o => !judgeNumber(o) && o.size === 3);

				for (const towMapList of [smallTwoMapList, xAxisTwoMapList, yAxisTwoMapList]) {
					for (const a of towMapList) {
						for (const b of towMapList) {
							if (a !== b && Array.from(a).every(o => b.has(o))) {
								b.forEach(o => { valueSet.add(o); });
							}
						}
					}
				}

				for (const [threeMapList, towMapList] of [[smallThreeMapList, smallTwoMapList], [xAxisThreeMapList, xAxisTwoMapList], [yAxisThreeMapList, yAxisTwoMapList]]) {
					for (const a of threeMapList) {
						let count = 0;
						for (const b of towMapList) {
							if (Array.from(b).every(o => a.has(o))) {
								count++;
								if (count >= 2) {
									break;
								}
							}
						}
						for (const b of threeMapList) {
							if (a !== b && Array.from(b).every(o => a.has(o))) {
								count++;
								if (count >= 2) {
									break;
								}
							}
						}
						if (count >= 2) {
							a.forEach(o => { valueSet.add(o); });
						}
					}
				}

				valueSet.forEach(other => { value.delete(other); });

				let isFinish = false;
				if (value.size === 1) {
					map[y][x] = Array.from(value)[0];
					isFinish = true;
				} else {
					for (const v of Array.from(value)) {
						if (!smallSet.has(v) || !xAxisSet.has(v) || !yAxisSet.has(v)) {
							map[y][x] = v;
							isFinish = true;
							break;
						}
					}
				}

				if (isFinish) {
					untreated_count--;
				}
			}
		}

		return untreated_count;
	};


	const parse = function () {
		// http://zh.sudoku.menu/

		/*
		const element_list = Array.from(document.querySelectorAll(".sudoku input+input"));
		const list = element_list.map(input => input.value.length === 0 ? 0 : parseInt(input.value));
		 */

		const list = [
			2, 6, 0,/**/ 0, 4, 0,/**/ 0, 0, 9,
			4, 0, 0,/**/ 0, 0, 0,/**/ 3, 6, 0,
			0, 0, 0,/**/ 0, 0, 0,/**/ 0, 0, 1,
			0, 0, 2,/**/ 3, 0, 0,/**/ 0, 1, 0,
			3, 0, 0,/**/ 9, 0, 7,/**/ 0, 0, 8,
			0, 5, 0,/**/ 0, 0, 4,/**/ 7, 0, 0,
			9, 0, 0,/**/ 0, 0, 0,/**/ 0, 0, 0,
			0, 7, 8,/**/ 0, 0, 0,/**/ 0, 0, 2,
			1, 0, 0,/**/ 0, 9, 0,/**/ 0, 4, 5];

		const parse_list = list.map(o => judgeNumber(o) && o !== 0 ? o : getFullValueSet());

		const map = array_split(parse_list, 9);
		// draw(map);

		let zeor_count = 0;
		let last_count = 0;
		while (true) {
			const count = parseOne(map);

			if (count === 0) {
				console.log("判断成功");
				draw(map);
				// finish(element_list, map);
				break;
			}
			if (last_count === count) {
				zeor_count++;
				if (zeor_count > 100) {
					console.log("判断失败");
					draw(map);
					break;
				}
			}
			last_count = count;
		}

	};

	/**
	 * @param element_list { HTMLInputElement[] }
	 * @param map { sudoku_map }
	 */
	const finish = function (element_list, map) {
		for (let y = 0; y < 9; y++) {
			for (let x = 0; x < 9; x++) {
				const value = map[y][x];
				const index = y * 9 + x;
				const element = element_list[index];
				if (element.value === "") {
					element.value = value.toString();
				}
			}
		}
		document.querySelector("body > div > div.cont > form").submit();
	};

	parse();
</script>